1. Technical Field
This invention relates to optimization of a compiler. More specifically, the invention relates to reducing the amount of spill code for frequently executed regions of program code.
2. Description Of The Prior Art
A control flow graph is a directed graph that represents the control flow of program code. The control flow graph includes a plurality of nodes and a directed edge. Each node represents a straight line sequence of code that can be entered only at the beginning and exited only at the end, i.e. a basic block. A directed edge is a control flow from one basic block to another basic block. FIG. 1 is a prior art diagram (1) of a basic control flow graph. As shown there are a plurality of basic blocks. The first basic block (12) introduces and defines variables a and b. From the first basic block, there is a decision point that enables the flow to proceed to one of two subsequent blocks (14) and (16). Separate edges (22) and (24) represent the control flow from the first basic block (12) to one of the two subsequent blocks (14) and (16). The edges (22) and (24) emanating from the first basic block (12) define a fork point, which is a point from which multiple edges branch in the control flow graph. Following completion of the instructions at either block (22) or (24) the control flow is directed to a final basic block (18). Again, there are two edges (26) and (28) that join at the final basic block. The point at which edges (26) and (28) join is known as a joint point, which is a point into which multiple edges merge in the control flow graph.
Register allocation is an important phase of compiling computer code. It maps variables to either registers or memory locations in a manner that minimizes the number of accesses to memory during program execution. By assigning frequently accessed variables to hardware registers, the number of memory references is reduced. Programs that utilize variables stored in hardware registers execute faster than programs that utilize variables stored in memory. It is known in the art that processors have a limited number of registers, and programs frequently have more variables than registers. A graph, known as an interference graph is used to assign temporary variables to hardware registers. In an interference graph, a node represents a live range and an edge represents the interference where two live ranges overlap. A live range of a variable is a range between an instruction where the variable is defined and another instruction where the variable is used or not used. This graph is known as an interference graph because the values would interfere with each other if they shared a register. Graph coloring is a prior art technique that assigns colors to the nodes in an interference graph such that neighboring nodes do not share a color, i.e. any two nodes connected by an edge must be colored with different registers. If two variables do not interfere, the same register may be used for both of them, thus reducing the number of registers needed. The same color, i.e. register, cannot be assigned to any two nodes that are connected by an edge.
Spilling is a process of placing a node, i.e. a live range, in memory when any register is not available. Reducing the amount of spill code in frequently executed program regions is critical to achieve high performance. There are different types of spill techniques. One type is known as the spill everywhere technique where an entire live range is placed in memory. However, this technique generates redundant spill code regardless of whether it is in a frequently executed program region. High performance is attained when a live range is placed in a register instead of memory in frequently executed program region. Another approach is to spill some parts of a live range into memory. This technique, starts spilling the live ranges after all the physical registers are used up. However, this technique may not select the optimal parts of live ranges since it does not prioritize the parts of live ranges that are associated with frequently executed program regions. A further approach that takes into account the spill everywhere technique and the partial spilling technique is known as a live-range splitting technique. This technique splits a live range into smaller sub-ranges before assigning any of the nodes to a registers. When a live range x is split into two sub-ranges x1 and x2, a copy is created to move a value from the source variable living in x1 to the target variable living in x2. This approach allows selection of the best sub-range for spilling among the sub-ranges that are split from different live ranges. However, there are limitations with this technique including that each sub-range must have at least one definition or use except for copies, copies might be inserted in hot regions, i.e. frequently executed regions of code, and many copies are sequentially inserted. Accordingly, as explained herein there are limitations associated with the prior art techniques that may increase the amount of interference and degrade coloring results.
Therefore, there is a need for a live-range splitting algorithm that reduces the amount of spill code in frequently executed regions of code.